// 版权所有2021 Go作者。版权所有。
// 此源代码的使用受BSD样式的约束
// 可以在许可证文件中找到的许可证。

package ssa

// fuseBranchRedirect检查出站分支所在的CFG
// 可以从其前一个If块派生If块的
// 在某些情况下，我们可以将前置If块重定向到
// 直接对应后续块。例如：
// p:
// v11=Less64<bool>v10 v8
// 如果v11转到b或u
// b:<-p。。。
// v17=Leq64<bool>v10 v8
// 如果v17转到其他o
// 我们可以直接将p重定向到s。
// None
// 这里的实现借用了prove-pass的框架。
// 1，遍历函数f的所有块以查找If块。
// 2，对于任何If块b，遍历其所有前置块以查找If块。
// 3、对于任何If块前置p，更新关系p->b。
// 4，遍历b的所有继承者。
// 5、对于b的任何后续s，如果a
// 矛盾被发现，然后将p重定向到b的另一个后继者。
func fuseBranchRedirect(f *Func) bool {
	ft := newFactsTable(f)
	ft.checkpoint()

	changed := false
	for i := len(f.Blocks) - 1; i >= 0; i-- {
		b := f.Blocks[i]
		if b.Kind != BlockIf {
			continue
		}
		// b为空或仅包含控制值。
		// TODO:如果b仅包含OpCopy或OpNot与b.控件相关，
		// 例如Copy（Not（Copy（Less64（v1，v2））），也许可以对其进行优化。
		bCtl := b.Controls[0]
		if bCtl.Block != b && len(b.Values) != 0 || (len(b.Values) != 1 || bCtl.Uses != 1) && bCtl.Block == b {
			continue
		}

		for k := 0; k < len(b.Preds); k++ {
			pk := b.Preds[k]
			p := pk.b
			if p.Kind != BlockIf || p == b {
				continue
			}
			pbranch := positive
			if pk.i == 1 {
				pbranch = negative
			}
			ft.checkpoint()
			// 假设采用分支p->b。
			addBranchRestrictions(ft, p, pbranch)
			// 根据上述条件检查是否有任何传出分支无法访问。
			parent := b
			for j, bbranch := range [...]branch{positive, negative} {
				ft.checkpoint()
				// 尝试更新关系b->child，并检查是否出现矛盾。
				addBranchRestrictions(ft, parent, bbranch)
				unsat := ft.unsat
				ft.restore()
				if !unsat {
					continue
				}
				// 这个分支是不可能的，所以将p直接重定向到另一个分支。
				out := 1 ^ j
				child := parent.Succs[out].b
				if child == b {
					continue
				}
				b.removePred(k)
				p.Succs[pk.i] = Edge{child, len(child.Preds)}
				// 修正b中的Phi值以减少一个参数。
				for _, v := range b.Values {
					if v.Op != OpPhi {
						continue
					}
					v.RemoveArg(k)
					phielimValue(v)
				}
				// 将子项设置为多个前置项。
				child.Preds = append(child.Preds, Edge{p, pk.i})
				ai := b.Succs[out].i
				for _, v := range child.Values {
					if v.Op != OpPhi {
						continue
					}
					v.AddArg(v.Args[ai])
				}
				if b.Func.pass.debug > 0 {
					b.Func.Warnl(b.Controls[0].Pos, "Redirect %s based on %s", b.Controls[0].Op, p.Controls[0].Op)
				}
				changed = true
				k--
				break
			}
			ft.restore()
		}
		if len(b.Preds) == 0 && b != f.Entry {
			// 布洛克现在死了。
			b.Kind = BlockInvalid
		}
	}
	ft.restore()
	ft.cleanup(f)
	return changed
}
